package cg.studio.practise;

import java.util.HashMap;
import java.util.Map;

/**
 * find the sub-array of an array ( only have 0 or 1 ), after fliped the sub-array, the array have most 1.
 * This problem can be changed to as 
 * find sub-array, max( count(0) - count(1) )
 * 
 * treat 0 as -1
 *  1, 1, 1, 0, 0, 0, 0, 1, 1, 1,1,1,0,0,0,1
 *             /\
 *    /\      /  \
 *   /  \    /    \/
 *  /    \  /
 *        \/
 *        
 * 0,0,0,1,1,0,0,0,1
 * \
 *  \  /\
 *   \/  \
 *        \/
 * 
 * the sub-array should 
 * start with zero and end with zero
 * 
 * in fact, the sub-array should 
 *   - from max to min 
 *   - index of max less than index of min
 * 
 * the basic steps are:
 *   - find the max-sum( if the current value is -1, then, this is the max-sum )
 *   - mark the state as found max, and finding min-sum( if the following value is 1, then this is the min-sum )
 *   - calculate diff between max-sum and min-sum, if the diff larger than previous max-diff, replace max-diff
 *   - go on calculate the sum, until meet sum > max-sum or sum < min-sum
 *     - if( sum < min-sum ), change the max-diff
 *     - if( sum > max-sum ), which means found another possible start point, keep previous information: max-diff 
 *       and go-on do the step same as find first max-sum
 *     
 * or we can only calculate the diff after find the max-sum, keep the max-diff and when diff < 0 means reach another max-sum  
 */

public class Flip
{
  public static void main( String[] argvs )
  {
    int arrs[][] = 
    { 
      {1, 0, 0, 1, 0, 0, 1, 0 }, //flipped {1, 1, 1, 0, 1, 1, 1, 0 }   6, 3
      {0, 0, 0, 0, 0, 0, 0, 0 }, //flipped {1, 1, 1, 1, 1, 1, 1, 1 }   8, 8
      {1, 1, 1, 1, 1, 1, 1, 1  }, //flipped {1, 1, 1, 1, 1, 1, 1, 1 }   8, 0
      {1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0,  1  }, //flipped {1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1,  1   }   10, 3
    };

    Map< Integer, SubArrayEnv > subArrays = new HashMap< Integer, SubArrayEnv >();
    subArrays.put( 0, new SubArrayEnv( 1, -2, 0, 5 ) );
    subArrays.put( 1, new SubArrayEnv( 0, -8, 0, 7 ) );
    subArrays.put( 2, null );
    subArrays.put( 3, new SubArrayEnv( 2, -1, 7, 12 ) );    // getFlipSubArray() failed in this case
    
    Map< Integer, Integer > countMap = new HashMap< Integer, Integer>();
    countMap.put( 0, 3 );
    countMap.put( 1, 8 );
    countMap.put( 2, 0 );
    countMap.put( 3, 3 );
    
    for( int index=0; index<arrs.length; ++index )
    {
      SubArrayEnv subArray = getFlipSubArray( arrs[index] );
      if( subArray == subArrays.get( index ) || ( subArray != null && subArray.equals( subArrays.get( index ) ) ) )
      {
        System.out.println( "valid: index: " + index );
        
      }
      else
      {
        System.out.println( "Invalid: array index: " + index + "; exepect = " + subArrays.get( index ) + "; actually is: " + subArray );
      }
    }
    
    System.out.println( "Done with validate of SubArray" );
    
    for( int index=0; index<arrs.length; ++index )
    {
      int count = maxFlippedCount( arrs[index] );
      if( count == countMap.get( index ) )
      {
        System.out.println( "valid: index: " + index );
        
      }
      else
      {
        System.out.println( "Invalid: array index: " + index + "; exepect = " + countMap.get( index ) + "; actually is: " + count );
      }
    }
    
    System.out.println( "Done with validate of SubArray" );
  }
  
  public static int maxFlippedCount( int[] arr )
  {
    int maxDiff = 0;
    int diff = 0;
    boolean foundStart = false;
    for( int index=0; index<arr.length; ++index )
    {
      if( !foundStart )
      {
        if( arr[index] == 0 )
        {
          //possible start
          foundStart = true;
          diff = 1;
          if( maxDiff == 0 )
            maxDiff = 1;
        }
      }
      else
      {
        diff += ( ( arr[index] == 0 ) ? 1 : -1 );
        if( diff > maxDiff )
          maxDiff = diff;
        
        if( diff < 0 )
        {
          //start with another start
          foundStart = false;
        }
      }
    }
    return maxDiff;
  }
  
  public static SubArrayEnv getFlipSubArray( int[] arr )
  {
    int maxIndex = 0;
    int max = 0;
    int minIndex = 0;
    int min = -1;
    int sum = 0;
    
    SubArrayEnv subArray = null;
    for( int i=0; i<arr.length; ++i )
    {
      sum += ( arr[i] == 0 ) ? (-1) : 1;
      if( sum > max )
      {
        if( maxIndex < minIndex )
        {
          //current max is large than the previous one and previous max got before min, this is a possible sub-array 
          if( subArray == null || subArray.max-subArray.min < max - min )
            subArray = new SubArrayEnv( max, min, maxIndex, minIndex );
          
          minIndex = -1;
        }
        max = sum;
        maxIndex = i;
      }
      else if( sum < min )
      {
        min = sum;
        minIndex = i;
      }
    }
    if( maxIndex < minIndex && ( subArray == null || subArray.max-subArray.min < max - min ) )
      subArray = new SubArrayEnv( max, min, maxIndex, minIndex );
    
    return subArray;
  }
  
  public static class SubArrayEnv
  {
    public SubArrayEnv( int max, int min, int maxIndex, int minIndex )
    {
      this.max = max;
      this.min = min;
      this.maxIndex = maxIndex;
      this.minIndex = minIndex;
    }
    int max;
    int min;
    int maxIndex;
    int minIndex;
    
    @Override
    public boolean equals( Object obj )
    {
      if( obj == null || !( obj instanceof SubArrayEnv ) )
        return false;
      SubArrayEnv another = (SubArrayEnv)obj;
      return another.max==max && another.min==min && another.maxIndex==maxIndex && another.minIndex==minIndex;
    }
    
    public String toString()
    {
      return "max=" + max + "; min=" + min + "; maxIndex=" + maxIndex + "; minIndex=" + minIndex ;
    }
  }
}
